#ifndef _GRAPH_AND_TREE_H_
#define _GRAPH_AND_TREE_H_
#include <vector>
#include <string>
#include "kaldi-math.h"

using namespace std;

namespace GRAPHTREE{


	typedef long long int StateId;
	typedef long long int ArcId;
	typedef long long int LinkId;
	typedef long long Int64;
	typedef long int Int32;

	////////////////////class and type declarations and normal functions ////////////
	class Arc;
	class State;
	class Token;
	class WFSTGraph;
	

	class TreeNode;
	typedef class TreeLink;
	
	class NormalTree;


	int SplitString(const std::string& s, std::vector<std::string>& s_parts);

	//////////////////////////////////////////////////////////////////////////

	class State{
		typedef long long int Int64;
	public:
		State();
		virtual ~State();

		void SortArcs();
		Arc* AddArc(Arc* new_arc);
		Int64 StateId(){
			return stateId_;
		}
		inline float GetWeight(){
			return weight_;
		}
		inline void SetWeight(float weight)
		{
			weight_ = weight;

		}

	public:
		State* tail;

	private:
		std::vector<Arc*> arcs_;
		Int64 stateId_;
		float weight_;


	};


	class Arc{
	public:
		Arc(int start, int end, char* ilabel, char* olabel, float weight):mStartId_(start),
			mEndId_(end), mIlabel_(ilabel), mOlabel_(olabel){
				mWeight_ = weight;
		};
		virtual ~Arc();

		inline void SetArcStartId(StateId id)
		{
			mStartId_ = id;
		}

		inline void SetArcEndId(StateId id)
		{
			mEndId_ = id;
		}

		inline void SetIlabel(std::string ilabel)
		{
			mIlabel_ = ilabel;
		}
		inline void SetOlabel(std::string olabel)
		{
			mOlabel_ = olabel;
		}

		inline void SetWeight(float weight)
		{
			mWeight_ = weight;
		}


		virtual inline int GetArcId(){
			return mArcId_;
		}
		virtual inline int NextStateId(){
			return mEndId_;
		}

		virtual inline int PrevStateId(){
			return mEndId_;
		}

		virtual inline float Weight(){
			return mWeight_;
		}
		inline std::string ILabel(){
			return mIlabel_;
		}

		inline std::string OLabel(){
			return mOlabel_;
		}
	public:
		Arc* tail;
	private:
		int mArcId_;
		int mStartId_;
		int mEndId_;
		float mWeight_;
		std::string mIlabel_;
		std::string mOlabel_;
	};


	class Token{
	public:
		Token();
		~Token();
	public:
		Token* tail;

	private:
		int tokenIndex_;

	};

	class WFSTGraph{
		typedef long long int StateId;
		typedef long long int LinkId;

	public:
		WFSTGraph();
		virtual ~WFSTGraph();
		
		virtual void InitGraph();
		virtual void RunBackForward();
		virtual float ComputeLMScore();
		virtual float Compute1Best();
		virtual void Arpa2fst(const char* arpa_file);
	protected:
		void FindSccs(State* graph_root, std::vector<State*>& sccs);

	};
	template <typename Elem>
	class FstGraph : public WFSTGraph
	{
		

	public:
		FstGraph():WFSTGraph(){};
		FstGraph(const char* fst_file_name);
		virtual ~FstGraph();

		void InitGraph();
		void AddArc2State(StateId state_id, Arc* new_arc);
		void Arpa2fst(const char* arpa_file);


	protected:
		//some useful algorithms
		void FindSccs(State* graph_root, std::vector<State*>& sccs);
		void Read(const std::string& fst_file_name, bool is_binary = true);
		float SingleSourceShortestPath(State* src, State** dst_state);

		//some tool functions for LM Computation

		State* FindState(Int64 state_id){
			if (states_list_)
			{
				State* this_state = states_list_, next_state;
				while(this_state != nullptr && this_state != state_free_head_){
					next_state = this_state->tail;
					if (this_state->StateId() == state_id)
					{
						return this_state;
					}
					this_state = next_state;
				}
			}
			return nullptr;
		}



		//for information management, arc and state and token manager
		//delete anyone from vector and push back to the memory list
		
		void DeleteState(State* state){
			if (state_free_head_->tail = nullptr)
			{
				state_free_head_->tail = state;
				state->tail = nullptr;
			}else{
				state->tail = state_free_head_->tail;
				state_free_head_->tail = state;
			}
		}
		void DeleteArc(Arc* arc){
			if (arc_free_head_->tail = nullptr)
			{
				arc_free_head_->tail = arc;
				arc->tail = nullptr;
			}else{
				arc->tail = arc_free_head_->tail;
				arc_free_head_->tail = arc;
			}
		}
		void DeleteToken(Token* tok){
			;
		}

		void ResizeStates(Int64 size){
			if (size > mStates.size())
			{
				Int64 orignal_size = mStates.size();
				mStates.resize(size);
				for (Int64 i=orignal_size;i<size;i++)
				{
					mStates[i] = New<State>();
				}
			}
		}

		void ResizeArcs(Int64 size){
			if (size > mArcs.size())
			{
				Int64 orignal_size = mArcs.size();
				mArcs.resize(size);
				for (Int64 i=orignal_size;i<size;i++)
				{
					mArcs[i] = New<Arc>();
				}
			}
		}

		State* NewState(StateId state_id){
			if (state_id >= mStates.size())
			{
				Int64 c= RoundUpToNearestPowerOfTwo(state_id);
				ResizeStates(c);
			}
			return mStates[state_id];
		}

		Arc* NewArc(ArcId arc_id){
			if (arc_id >= mArcs.size())
			{
				Int64 c = RoundUpToNearestPowerOfTwo(arc_id);
				ResizeArcs(c);
			}
			return mArcs[arc_id];
		}


		//for real memory management
		Elem* AllocateList(Int64 new_size){
			Int64 size = RoundUpToNearestPowerOfTwo(new_size);
			Elem* elem = new Elem[size];
			for (Int64 i=0;i<size;i++)
			{
				elem[i].tail = elem + i +1;
			}
			elem[size-1] = nullptr;
			return elem;
		}
		void FreeList(Elem* list_head){
			if (list_head)
			{
				Elem* curr = list_head, * next;
				while(curr){
					next = curr->tail;
					delete curr;
					curr = next;
				}
			}
		}

		Arc* New(){
			Arc* new_arc = nullptr;
			if (arcs_list_ == nullptr)
			{
				arcs_list_ = AllocateList<Arc>(1024);
				arc_free_head_ = arcs_list_;
				return New();
			}
			if (arc_free_head_->tail == nullptr)
			{
				//new a list
				Arc* new_allc = AllocateList<Arc>(1024);
				arc_free_head_->tail = new_allc;
				new_arc = arc_free_head_;
				arc_free_head_= arc_free_head_->tail;
				return new_arc;
			}
			new_arc = arc_free_head_;
			arc_free_head_ = arc_free_head_->tail;
			return new_arc;
		}
		State* New(){
			State* new_state = nullptr;
			if (states_list_ == nullptr)
			{
				states_list_ = AllocateList<State>(1024);
				new_state = states_list_;
				state_free_head_ = states_list_->tail;
				return new_state;
			}
			if (state_free_head_->tail == nullptr)
			{
				//new a list
				State* new_allc = AllocateList<State>(1024);
				state_free_head_->tail = new_allc;
				new_state = state_free_head_;
				state_free_head_= state_free_head_->tail;
				return new_state;
			}
			new_state = state_free_head_;
			state_free_head_ = state_free_head_->tail;
			return new_state;
		}

	private:
		StateId mStart; // start state of fst
		StateId mEnd;  // end state of fst
		/////////////////for information management, arc and state manager/////////////////////////////////
		std::vector<State*> mStates;
		std::vector<Arc*> mArcs;
		std::vector<Token*> mTokens;

		StateId mFreeNodeStart;
		LinkId mFreeArcStart;


		///////////////////they are real memory manager/////////////////////////////////
		//for states
		State* states_list_;
		State* state_free_head_;
		//for arcs
		Arc* arcs_list_;
		Arc* arc_free_head_;

		//for tokens
		Token* token_list_;
		Token* token_free_head_;

		//some useful constants
		static Int64 elementAlloc_;
		



	};// end of definition of fst graph

	//////////////////////////////////////////////////////////////////////////

	template <typename Elem>
	class HashFactory{
	public:
		HashFactory(){};
		~HashFactory();

		void SetSize(size_t new_size); //init and allocate the first elements
		Elem* NewElem();//get a element
		Elem* Find(size_t key); //find some element
		void DeleteElem(size_t key);


	private:
		Elem* hash_list_head_;
		std::vector<Elem*> allocated_;

		static int sAllocated_size;


	};



	class TreeLink{
	public:
		TreeLink(){};
		TreeLink(int start, int end, float weight):
		mStart(start), mEnd(end), mWeight(weight){};
		virtual ~TreeLink(){};
		virtual int PrevStateID() const {
			return mStart;
		}
		virtual int NextStateID() const {
			return mEnd;
		}
		inline float Weight() const {
			return mWeight;
		}
		inline TreeNode* PrevNode() const {
			return prev_node;
		}

		inline TreeNode* NextNode() const {
			return next_node;
		}

		inline TreeNode* SetPrevNode(TreeNode * node){
			prev_node = node;
			return prev_node;
		}

		inline TreeNode* SetNextNode(TreeNode * node){
			next_node = node;
			return next_node;
		}

	public:
		TreeLink* tail;
		TreeNode* prev_node;
		TreeNode* next_node;
	private:
		float mWeight;
		int mStart;
		int mEnd;

	};

	class TreeNode{
	public:
		TreeNode():mIndex(0), tail(nullptr){
			mOutLinks.clear();
		};
		virtual ~TreeNode(){};
		const std::vector<TreeLink*>& GetOutLinks() const{
			return mOutLinks;
		}
		int GetNodeIndex() const {
			return mIndex;
		}
		TreeLink* AddLink(TreeLink* new_link){
			if (new_link)
			{
				mOutLinks.push_back(new_link);
				SortLinks();
			}
			return new_link;
		}
	protected:
		inline void SortLinks(){
			//sort links by weight, here we used insert sorting algorithm
			for (int i=1;i<mOutLinks.size();i++)
			{
				int j = i;
				while (j > 0 && mOutLinks[j-1]->Weight() > mOutLinks[j]->Weight())
				{
					TreeLink* tmp = mOutLinks[j];
					mOutLinks[j] = mOutLinks[j-1];
					mOutLinks[j-1] = tmp;
					j--;
				}
				
			}
		}
	public:
		TreeNode* tail;
	private:
		int mIndex;
		std::vector<TreeLink*> mOutLinks;
		
	};





	class NormalTree{
		
	public:
		NormalTree():mTreeRoot(nullptr), mNodeHead(nullptr), mLinkHead(nullptr),
		mFreeLink(-1), mFreeNode(-1){
			
		};
		virtual ~NormalTree();


		void ConstructTree(const std::string& file_name);
		void DfsTree(TreeNode* curr_root, void* hook_ptr);
		TreeNode* Dfs(TreeNode* curr_root, int node_index){
			if (curr_root)
			{
				if(curr_root->GetNodeIndex() == node_index){
					return curr_root;
				}else{

				}
			}
		}
		TreeNode* FindNode(TreeNode* root,  int node_index){
			if (root)
			{
				if (root->GetNodeIndex() == node_index)
				{
					return root;
				}else{
					const std::vector<TreeLink*>& arcs = root->GetOutLinks();
					std::vector<TreeLink*>::const_iterator arc_it = arcs.begin(), end = arcs.end();
					for (;arc_it != end;arc_it++)
					{
						TreeNode* end_node = (*arc_it)->NextNode();
						TreeNode* rt = Dfs(end_node, node_index);
						if (rt != nullptr)
						{
							return rt;
						}
					}
				}
				return Dfs(mTreeRoot, node_index);
			}
			return mTreeRoot;
		}
		TreeLink* AddLink2Node(TreeNode* node, TreeLink* new_link){
			if (new_link)
			{
				node->AddLink(new_link);
			}
			return new_link;
		}

		inline void SetLinksSize(int new_size){
			if (new_size > mTreeLinks.size())
			{
				int old_size = mTreeLinks.size();
				int added_size = new_size-old_size;
				mTreeLinks.resize(new_size);
				TreeLink* new_allocated = new TreeLink[added_size];
				if (old_size == 0)
				{
					mLinkHead = new_allocated;
				}
				for (int i=0;i<added_size-1;i++)
				{
					new_allocated[i].tail = new_allocated+i+1;
					mTreeLinks[old_size+i] = &(new_allocated[i]);
				}
				new_allocated[added_size-1].tail = nullptr;
			}
		}
		inline void SetNodesSize(int new_size){
			if (new_size > mTreeNodes.size())
			{
				int old_size = mTreeNodes.size();
				int added_size = new_size-old_size;
				mTreeNodes.resize(new_size);
				TreeNode* new_allocated = new TreeNode[added_size];
				if (old_size == 0)
				{
					mNodeHead = new_allocated;
				}
				for (int i=0;i<added_size-1;i++)
				{
					new_allocated[i].tail = new_allocated+i+1;
					mTreeNodes[old_size+i] = &(new_allocated[i]);
				}
				new_allocated[added_size-1].tail = nullptr;
				
			}
		}

		TreeNode* NewNode(){
				TreeNode* free_node = nullptr;
			if (mFreeNode < mTreeNodes.size())
			{
				free_node = mTreeNodes[mFreeNode];
				mFreeNode++;
				return free_node;
			}else{
				if (mFreeNode >= mTreeNodes.size())
				{
					this->SetNodesSize(mTreeNodes.size()*2);
				}
				return this->NewNode();
			}
		};

		TreeLink* NewLink(){
			TreeLink* free_link = nullptr;
			if (mFreeNode < mTreeNodes.size())
			{
				free_link = mTreeLinks[mFreeLink];
				mFreeLink++;
			}else{
				if (mFreeLink >= mTreeLinks.size())
				{
					this->SetLinksSize(mTreeLinks.size()*2);
				}
				return this->NewLink();
			}
		};

		TreeLink* GetLink(int link_index){
			if (link_index < mTreeLinks.size())
			{
				return mTreeLinks[link_index];
			}else{
				SetLinksSize(link_index+100);
				return mTreeLinks[link_index];
			}
			return nullptr;
		}

		TreeNode* GetNode(int node_index){
			if (node_index < mTreeNodes.size())
			{
				return mTreeNodes[node_index];
			}else{
				SetNodesSize(node_index+100);
				return GetNode(node_index);
			}
		}



	private:
		TreeNode* mTreeRoot;
		std::vector<TreeNode*> mTreeNodes;
		std::vector<TreeLink*> mTreeLinks;
		TreeLink* mLinkHead;
		TreeNode* mNodeHead;
		int mFreeNode;
		int mFreeLink;
		static int sNodeAllc;
		static int sLinkAllc;


	};

	int NormalTreeRun(int argc, char* argv[]);
} //end of namespace GRAPHTREE



#endif